/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool FindPath(TreeNode* root, TreeNode* aim, stack<TreeNode*>& path) {
        if (root == nullptr)return false;

        path.push(root);
        if (root == aim)return true;

        if (FindPath(root->left, aim, path))return true;
        if (FindPath(root->right, aim, path))return true;

        path.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> p_path;
        stack<TreeNode*> q_path;
        FindPath(root, p, p_path);
        FindPath(root, q, q_path);
        while (p_path.size() != q_path.size()) {
            if (p_path.size() > q_path.size()) {
                p_path.pop();
            }
            else {
                q_path.pop();
            }
        }
        while (q_path.top() != p_path.top()) {
            q_path.pop();
            p_path.pop();
        }
        return q_path.top();
    }
};